/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/two-sum
   @Language: C++
   @Datetime: 16-02-09 08:41
   */

class Solution {
public:
	/*
	 * @param numbers : An array of Integer
	 * @param target : target = numbers[index1] + numbers[index2]
	 * @return : [index1+1, index2+1] (index1 < index2)
	 */
	/* Tips: find any pair is ok not all pairs.
	 *       using hash map to store the num value and index
	 * notice: if the target is 4 and the answer expection num 2 + 2,
	 *         only the one num 2 is stored in hash map, but also work ok!
	 *         because must have the other num 2 is not in hash map!
	 * Index begin from 1 to n, not 0 to n-1
	 * */
	vector<int> twoSum(vector<int> &nums, int target) {
		// write your code here
		unordered_map<int,int> hash;	// val+id
		// we can search num and insert it to hash map at same time
		// and current num must be not in hash map
		for(int i=nums.size(); i--; hash[nums[i]]=i)
			if (hash.find(target-nums[i]) != hash.end())
				return {1+i,1+hash[target-nums[i]]};
		return {0,0};					// no answer return {0,0}
	}
};
